package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author durant
 * @create 2021-11-15 12:45
 */
public class ShellSort {
    public static void main(String[] args) {
//        int[] arr =  {8,9,1,7,2,3,5,4,6,0};
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 8000000);
        }
        Date date1 = new Date(System.currentTimeMillis());
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("hh:mm:ss.SSS");
        String format = simpleDateFormat.format(date1);
        shellSort2(arr);
        Date date2 = new Date(System.currentTimeMillis());
        String forma2 = simpleDateFormat.format(date2);
        System.out.println("排序前的时间：" + format);
        System.out.println("排序后的时间：" + forma2);

    }
    public static void shellSort(int[] arr){
        int count = 0;
        int temp = 0;
        // 使用循环处理
        for (int gap = arr.length/2 ; gap >0 ; gap /= 2){
            for (int i = gap; i < arr.length; i++) {
                // 遍历各组中所有的元素，共5组，每组两个元素，补步长为5
                for (int j = i -gap; j >= 0 ; j-=gap) {
                    // 如果当前的元素大于加上步长的元素，那么就进行交换
                    if (arr[j] > arr[j+gap]){
                        temp = arr[j+gap];
                        arr[j+gap] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
            count++;

        }
        /*
        // 第一轮
        // 将10个数据分为 10/2=5
        int temp = 0;
        for (int i = 5; i < arr.length; i++) {
            // 遍历各组中所有的元素，共5组，每组两个元素，补步长为5
            for (int j = i -5; j >= 0 ; j-=5) {
                // 如果当前的元素大于加上步长的元素，那么就进行交换
                if (arr[j] > arr[j+5]){
                    temp = arr[j+5];
                    arr[j+5] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
        // 第二轮
        // 将10个数据分为 5/2=2
        for (int i = 2; i < arr.length; i++) {
            // 遍历各组中所有的元素，共5组，每组两个元素，补步长为5
            for (int j = i -2; j >= 0 ; j-=2) {
                // 如果当前的元素大于加上步长的元素，那么就进行交换
                if (arr[j] > arr[j+2]){
                    temp = arr[j+2];
                    arr[j+2] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println("第二轮：");
        System.out.println(Arrays.toString(arr));
        // 第三轮
        // 将10个数据分为 2/2=1
        for (int i = 1; i < arr.length; i++) {
            // 遍历各组中所有的元素，共5组，每组两个元素，补步长为5
            for (int j = i -1; j >= 0 ; j-=1) {
                // 如果当前的元素大于加上步长的元素，那么就进行交换
                if (arr[j] > arr[j+1]){
                    temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println("第三轮：");
        System.out.println(Arrays.toString(arr));*/
    }
    public static void shellSort2(int[] arr){
        // 使用循环处理
        int count = 0;
        for (int gap = arr.length/2 ; gap >0 ; gap /= 2){
            for (int i = gap; i < arr.length; i++) {
               // 从gap个元素，逐个对其所在的组进行排序
                int j =i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]){
                    while (j - gap >= 0 && temp < arr[j - gap]){
                        // 移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    // 当退出while时，就给temp找到插入的位置
                    arr[j] = temp;

                }
            }
            count++;



        }

    }
}
